package com.yubest;

/**
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * <p>
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * <p>
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 * <p>
 * 提示：
 * <p>
 * 0 <= x <= 2^31 - 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sqrtx
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/26 16:31
 */
public class P0069 {

    public static void main(String[] args) {
        System.out.println(new Solution69().mySqrt(4));

        System.out.println(new Solution69().mySqrt(2147395599));
    }
}

class Solution69 {

    /**
     * 思路：二分查找
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x == 1 || x == 2 || x == 3) {
            return 1;
        }
        int m = x / 2;
        int start = 1;
        int end = x;
        while (true) {
            //为何用除法？防止中间计算的结果溢出
            if (m <= x / m && (m + 1) > x / (m + 1)) {
                return m;
            }
            if (m <= x / m) {
                start = m + 1;
            } else {
                end = m - 1;
            }
            m = (start + end) / 2;
        }
    }
}
